package com.itheima.d02_binary_search;

import java.util.Arrays;

/**
 * 优化：二分查找
 */
public class Test {

    public static  int binarySearch(int[] arr, int value) {
        int left = 0;

        int right = arr.length - 1;
        while(left <= right){
            int mid =  ( right + left ) >>> 1;
            if(arr[mid] == value){
                return mid;
            }else if(arr[mid] > value){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        //前提：数组是有序的
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int index = binarySearch(arr, 55);
        System.out.println("查找结果："+ index);


        //问题：int mid = (left + right) / 2; 可能会超出int的范围，导致数据丢失
        /*
            int left = 0;
            int right = Integer.MAX_VALUE;
            //第一轮：取中间位置
            int mid =  (left + right) / 2;
            System.out.println("第一次获取中间值："+mid);

            //第二轮：取中间位置
            left = mid + 1;
            mid =  (left + right) / 2;
            System.out.println("第二次获取中间值："+mid);
        */


        //解决方案一：效率低
        /*
        int left = 0;
        int right = Integer.MAX_VALUE;
        //第一轮：取中间位置
        int mid =  left + (right-left)/2;
        System.out.println("第一次获取中间值："+mid);

        //第二轮：取中间位置
        left = mid + 1;
        mid =  left + (right-left)/2;
        System.out.println("第二次获取中间值："+mid);
        */

        //解决方案二：移位，效率高
        int left = 0;
        int right = Integer.MAX_VALUE;
        //第一轮：取中间位置
        int mid = (right+left)>>>1;
        System.out.println("第一次获取中间值："+mid);

        //第二轮：取中间位置
        left = mid + 1;
        mid = (right+left)>>>1;
        System.out.println("第二次获取中间值："+mid);


        Arrays.binarySearch(arr, 5);
    }



}
